#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int n, m;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        queue<PII> q;
        vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                q.push({ i,0 });

            }
            if (board[i][m - 1] == 'O') {
                q.push({ i,m - 1 });
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[0][i] == 'O') {
                q.push({ 0,i });
            }
            if (board[n - 1][i] == 'O') {
                q.push({ n - 1,i });
            }
        }

        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();
                int a = it.first;
                int b = it.second;
                board[a][b] = 'Y';
                st[a][b] = true;
                for (int j = 0; j < 4; j++) {
                    int x = dx[j] + a;
                    int y = dy[j] + b;
                    if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && !st[x][y]) {
                        board[x][y] = 'Y';
                        st[x][y] = true;
                        q.push({ x,y });
                    }
                }
            }
        }
        // for(auto it:board){
        //     for(auto itt:it){
        //         cout<<itt;
        //     }
        //     cout<<endl;
        // }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O')board[i][j] = 'X';
                if (board[i][j] == 'Y')board[i][j] = 'O';

            }
        }


    }
};